package com.sheng.leetcode.year2023.month02.day21;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/02/21
 * <p>
 * 1326. 灌溉花园的最少水龙头数目<p>
 * <p>
 * 在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。<p>
 * 花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。<p>
 * 给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：<p>
 * 如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。<p>
 * 请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 5, ranges = [3,4,1,1,0,0]<p>
 * 输出：1<p>
 * 解释：<p>
 * 点 0 处的水龙头可以灌溉区间 [-3,3]<p>
 * 点 1 处的水龙头可以灌溉区间 [-3,5]<p>
 * 点 2 处的水龙头可以灌溉区间 [1,3]<p>
 * 点 3 处的水龙头可以灌溉区间 [2,4]<p>
 * 点 4 处的水龙头可以灌溉区间 [4,4]<p>
 * 点 5 处的水龙头可以灌溉区间 [5,5]<p>
 * 只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 3, ranges = [0,0,0,0]<p>
 * 输出：-1<p>
 * 解释：即使打开所有水龙头，你也无法灌溉整个花园。<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 10^4<p>
 * ranges.length == n + 1<p>
 * 0 <= ranges[i] <= 100<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden">1326. 灌溉花园的最少水龙头数目</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1326 {

    @Test
    public void test01() {
//        int n = 5;
//        int[] ranges = {3, 4, 1, 1, 0, 0};
        int n = 3;
        int[] ranges = {0, 0, 0, 0};
        System.out.println(new Solution().minTaps(n, ranges));
    }
}

class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] last = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            // l 代表能覆盖到的最小的位子，r 代表右端点
            int l = Math.max(0, i - ranges[i]), r = i + ranges[i];
            // 将能覆盖当前位置的最远右端点放入数组 last 中
            last[l] = Math.max(last[l], r);
        }
        // ans 代表最少水龙头数目，mx 表示当前能覆盖的最远右端点，pre 表示上一个水龙头覆盖的最远右端点
        int ans = 0, mx = 0, pre = 0;
        for (int i = 0; i < n; i++) {
            mx = Math.max(mx, last[i]);
            // 无法覆盖到下一个位置
            if (mx <= i) {
                return -1;
            }
            // 需要使用一个新的子区间
            if (pre == i) {
                ans++;
                pre = mx;
            }
        }
        return ans;
    }
}
